#include<vector>
#include<iostream>

using namespace std;


 
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};



struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



//递归01：汉诺塔问题
class Solution1 {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        return dfs(A,B,C,A.size());    
    }

    void dfs(vector<int>& A, vector<int>& B, vector<int>& C,const int& n)
    {
        if(n==1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        dfs(A,C,B,n-1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B,A,C,n-1);
    }
};


//递归02：合并两个有序链表
class Solution2 {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        return ListMerge(list1,list2);
    }
    
    ListNode* ListMerge(ListNode* list1, ListNode* list2)
    {
        if(list1==nullptr)
            return list2;
        if(list2==nullptr)
            return list1;
        if(list1->val<list2->val)
        {
            list1->next=ListMerge(list1->next,list2);
        }
        else
        {
            list2->next=ListMerge(list1,list2->next);
        }
        return list1->val<list2->val?list1:list2;
    }
};

//递归03：反转链表
class Solution3 {
public:
    ListNode* reverseList(ListNode* head) 
    {
        return _reverseList(nullptr,head);
    }

    ListNode* _reverseList(ListNode* prev,ListNode* cur)
    {
        if(cur==nullptr)
            return nullptr;
        if(cur->next==nullptr)
        {
            cur->next=prev;
            return cur;
        }
        ListNode* next=cur->next;
        cur->next=prev;
        return _reverseList(cur,next);
    }
};

//递归04：两两交换链表中的节点
class Solution4 {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(head==nullptr)   return nullptr;
        return _swapPairs(head,head->next);
    }

    ListNode* _swapPairs(ListNode* prev,ListNode* cur)
    {
        if(cur==nullptr)
            return prev;

        ListNode* next=cur->next;
        cur->next=prev;
        if(next!=nullptr)
            prev->next=_swapPairs(next,next->next);
        else
            prev->next=nullptr;
        return cur;
    }
};

//递归05：快速幂
class Solution5 {
public:
    double myPow(double x, int n) 
    {
        long n1=n;
        if(n1<0)        
            return _myPow(1/x,-n1,1/x);
        else
            return _myPow(x,n1,x);         
    }

    double _myPow(double x, long n,double ret)
    {
        if(n==0)
            return 1;
        if(n==1)
            return ret;
        if(n%2==1)
            return _myPow(x,n-1,x*ret);
        else
            return _myPow(x*x,n/2,x*ret);
    } 
};


int main()
{
    return 0;
}